package com.lsa.letcode.the139.wordBreak;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
    	return canBeSegmented(prepare(s), dict, new HashMap<String, Boolean>());
    	
    }
    
    private boolean canBeSegmented(String s, Set<String> dict, Map<String, Boolean> memo) {
    	if (s == null || s.isEmpty()) {
    		return false;
    	}
    	// dp[i]=true means s[0,i] canBeSegmented
    	boolean[] dp = new boolean[s.length()];
    	dp[0] = dict.contains(s.substring(0, 1)); 
    	for (int i = 1; i < dp.length; i++) {
    		// check [0, i]
    		// [0, i]=true, 
    		// 		if 
    		//			[0,i] in dict
    		//			OR
    		//	 		$EXIST$ j in [0,i-1], s.t.  [0, j]=true AND [j+1, i] in dict.
    		//		
    		if (dict.contains(s.substring(0, i+1))) {
    			dp[i] = true;
    		}
    		else {
    			for (int j = 0; j < i; j++) {
    				if (dp[j] && dict.contains(s.substring(j + 1, i + 1))) {
    					dp[i] = true;
    					break;
    				}
    			}
    		}
		}
    	
    	return dp[s.length() - 1]; // s[0,s.length() - 1] canBeSegmented
    }
    
    private boolean canBeSegmentedDumb(String s, Set<String> dict, Map<String, Boolean> memo) {
    	if (s.length() < 1) {
    		return false;
    	}
    	Boolean cached = memo.get(s);
    	if (cached != null){
    		return cached;
    	}
		if (dict.contains(s)) {
    		return true;
    	}
    	for (int i = 0; i < s.length() - 1; i++) {
			String subStrLeft = s.substring(0, i + 1);
			boolean isSegmented = canBeSegmentedDumb(subStrLeft, dict, memo);
			memo.put(subStrLeft, isSegmented);
			if (isSegmented){
				String subStrRight = s.substring(i + 1);
				if ((subStrRight.isEmpty() || dict.contains(subStrRight))) {
					return true;
				}
			}
		}
    	return false;
    }
    
	private boolean canBeSegmented1(String s, Set<String> dict, Map<String, Boolean> memo) {
		if (s == null || s.length() < 1) {
    		return false;
    	}
    	
    	Boolean result = memo.get(s);
    	if (result != null){
    		return result;
    	}
    	
    	if (dict.contains(s)) {
    		return true;
    	}
    	
    	boolean isBreaks = false;
    	for (int i = 1; i < s.length(); i++) {
			String left = s.substring(0, i);
			boolean isBreaksLeft = canBeSegmented1(left, dict, memo);
			memo.put(left, isBreaksLeft);
			if (!isBreaksLeft) {
				continue;
			}
			String right = s.substring(i, s.length());
			boolean isBreaksRight = canBeSegmented1(right, dict, memo);
			memo.put(right, isBreaksRight);
			if (isBreaksLeft && isBreaksRight) {
				isBreaks = true;
    			break;
    		}
    	}
        return isBreaks;
	}
    
    private static String prepare(String s) {
    	if (s == null){
    		return s;
    	}
    	StringBuilder sb = new StringBuilder();
    	for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (!Character.isWhitespace(c)) {
				sb.append(c);
			}
		}
    	return sb.toString();
    }
}